package com.example.javabasic.suanfa.jiandan.反转链表;

/**
 * 双向链表反转
 */
public class Solution {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        Linked link = createLink(arr);
        Linked test = test(link);
        System.out.println(test);
        Linked linked = test2(link);
        System.out.println(linked);

    }
    //构建单向链表
    public static Linked createLink(int[] arr){
        Linked linked = new Linked(arr[0]);
        Linked next = linked;
        for (int i = 1; i < arr.length; i++) {
            next.next = new Linked(arr[i]);
            next = next.next;
        }
        return linked;
    }


    //反转链表 头插法1
    public static Linked test(Linked link){
        Linked res  = null;
        while(link!=null){
            System.out.println(res);
            Linked head = link;
            link = head.next;
            head.next = res;
            res = head;
        }
        return res;
    }


    /***
     * 头插法2  参考hashmap 头插  会反转链表
     *
     * @param link
     * @return
     */
    public static Linked test2(Linked link){
        Linked res = null;
        while(link!=null){
            //获取当前link 头部元素
            Linked head = link;
            //A链表 指针移动到后面一个
            link = link.next;
            //A链表取出的头 插入B链表头部
            head.next = res;
            //B链表头部定位到新的头
            res = head;
        }
        return res;

    }

}
